#ifndef part8
#define part8

void swap(int& a, int &b){
    int t = a;
    a = b;
    b= t;
}

// 插入排序
void insert_sort(int* list, int start, int end){
    int sentry = -1;
    int j =-1;
    for (int i = start + 1; i < end; i++){
        if (list[i] < list[i-1]){
            sentry = list[i];
            for (j = i - 1; i >= 0 && list[j] > sentry; j--)
            {
                list[j+1] = list[j];
            }
            list[j+1] = sentry;
        }
    }
}


// 选择排序
void select_sort(int* list, int start, int end){
    int min;
    for (int i = start; i < end; i++){
        min = i;
        for (int j = i + 1; j < end; j++){
            if (list[j] < list[min]){
                min = j;
            }
        }
        swap(list[i],list[min]);
    }
}
// 冒泡排序
void bubble_sort(int* list, int start, int end){
    bool flag = true;
    for (int i = start; i < end; i++){
        flag = true;
        for (int j = end - 2; j >= i; j--){
            if (list[j] > list[j+1]){
                swap(list[j],list[j+1]);
                flag = false;
            }
        }
        if (flag) return;
    }
}


// 快速排序
void q2_sort(int* list, int start, int end){
    if (end - start <= 1)return;
    swap(list[start],list[(start + end)/2]);
    int sentry = list[start];
    int left = start;
    int right = end-1;
    while(left != right){
        while(left != right && list[right] >= sentry)right--;
        list[left] = list[right];
        while(left != right && list[left] <= sentry)left++;
        list[right] = list[left];
    }
    list[left] = sentry;
    q2_sort(list, start, left);
    q2_sort(list, left+1, end);
}


// 希尔排序
void shell_sort(int* list, int start, int end){
    int sentry = -1;
    int j = -1;
    for (int dk = (end-start)/2; dk >= 1; dk /= 2)
    {
        for (int i = start + dk; i < end; i += dk){
            if (list[i-dk] > list[i]){
                sentry = list[i];
                for (j = i-dk; j >= 0 && list[j] > sentry; j -= dk)
                {
                    list[j+dk] = list[j];
                }
                    list[j+dk] = sentry;
            }
        }
    }
    
}

// 归并排序
int buffer[msize];
void merge(int* list, int start, int mid, int end)
{
    for (int i = start; i < end; i++){
        buffer[i] = list[i];
    }
    int i = start;
    int j = mid;
    int k = start;
    while (i < mid && j < end){
        list[k++] = buffer[i] <= buffer[j] ? buffer[i++] : buffer[j++];
    }   
    while (i < mid) list[k++] = buffer[i++];
    while (j < end) list[k++] = buffer[j++];
}

void merge_sort(int* list, int start, int end){
    if (end - start <= 1)return;
    int mid = (start + end)/2;
    merge_sort(list, start, mid);
    merge_sort(list, mid, end);
    merge(list, start, mid, end);
}

// 
int nth(int* list, int start, int end, int n){
    int sentry = list[start];
    int left = start;
    int right = end - 1;
    while(left != right){
        while(left != right && list[right] >= sentry)right--;
        list[left] = list[right];
        while(left != right && list[left] <= sentry)left++;
        list[right] = list[left];
    }
    list[left] = sentry;
    if (left + 1 == n){
        return list[left];
    }
    int ret = -1;
    if (left + 1 > n){
        ret = nth(list, start, left, n);
        if (ret != -1) return ret;
    }else{
        ret = nth(list, left+1, end, n);
        if (ret != -1) return ret;
    }
    return -1;
}
#endif